Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

摘要

We analyze the accuracy of the discrete least-squares approximation of afunction $u$ in multivariate polynomial spaces $\mathbb{P}_\Lambda:={\rm span}\{y\mapsto y^\nu \,: \, \nu\in \Lambda\}$ with $\Lambda\subset \mathbb{N}_0^d$over the domain $\Gamma:=[-1,1]^d$, based on the sampling of this function atpoints $y^1,\dots,y^m \in \Gamma$. The samples are independently drawnaccording to a given probability density $\rho$ belonging to the class ofmultivariate beta densities, which includes the uniform and Chebyshev densitiesas particular cases. We restrict our attention to polynomial spaces associatedwith \emph{downward closed} sets $\Lambda$ of \emph{prescribed} cardinality$n$, and we optimize the choice of the space for the given sample. Thisimplies, in particular, that the selected polynomial space depends on thesample. We are interested in comparing the error of this least-squaresapproximation measured in $L^2(\Gamma,d\rho)$ with the best achievablepolynomial approximation error when using downward closed sets of cardinality$n$. We establish conditions between the dimension $n$ and the size $m$ of thesample, under which these two errors are proven to be comparable. Our mainfinding is that the dimension $d$ enters only moderately in the resultingtrade-off between $m$ and $n$, in terms of a logarithmic factor $\ln(d)$, andis even absent when the optimization is restricted to a relevant subclass ofdownward closed sets, named {\it anchored} sets. In principle, this allows oneto use these methods in arbitrarily high or even infinite dimension. Ouranalysis builds upon [2] which considered fixed and nonoptimized downwardclosed multi-index sets. Potential applications of the proposed results arefound in the development and analysis of numerical methods for computing thesolution to high-dimensional parametric or stochastic PDEs.